package com.qisi.kandroidshalon.leetcode.xor;

import android.util.Log;

import com.qisi.kandroidshalon.leetcode.Util;

public class XOR {
    private static final String TAG = "XOR";

    /**
     * 数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
     */
    public static int missingNumber(Integer[] nums) {
        int xorSum = 0;
        for (int i = 0; i < nums.length + 1; i++) {
            xorSum ^= i;
            if (i < nums.length) {
                xorSum ^= nums[i];
            }
        }
        Log.i(TAG, "lossNum:" + xorSum);
        return xorSum;
    }


    /**
     * 面试题 16.01. 交换数字
     * 编写一个函数，不用临时变量，直接交换numbers = [a, b]中a与b的值。
     * <p>
     * 示例：
     * <p>
     * 输入: numbers = [1,2]
     * 输出: [2,1]
     * 提示：
     * <p>
     * numbers.length == 2
     * -2147483647 <= numbers[i] <= 2147483647
     * <p>
     * 思路: 利用异或的a^b^b = a 和交换律
     */
    public static Integer[] swapNumbers(Integer[] numbers) {
        numbers[0] ^= numbers[1];//a = a^b
        numbers[1] ^= numbers[0];//b = a^b^b = a
        numbers[0] ^= numbers[1];
        Util.dumpArray(numbers);//a = a^b^a = b
        return numbers;
    }

    /**
     * 260. 只出现一次的数字 III
     * 给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
     * <p>
     * 你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
     * <p>
     * 思路：利用异或，得到a^b的信息，然后a^b中为1的bit为表示a和b此位不相同，根据此位可以将数据分为两组，a和b一定分别在这两组里
     * 技巧: 提取n最右侧的1： n&((~n)+1)，
     * 然后分别拿a^b和分组数据进行异或，这样ab就能分离了
     */
    public static Integer[] singleNumber(Integer[] nums) {
        Integer[] result = new Integer[2];
        int xorSum = 0;
        for (int i = 0; i < nums.length; i++) {
            xorSum ^= nums[i];
        }

        int mask = xorSum & ((~xorSum) + 1);
        int tmp = xorSum;//暂存a^b
        for (int i = 0; i < nums.length; i++) {
            if ((mask & nums[i]) == 0) {
                xorSum ^= nums[i];
            }
        }
        result[0] = xorSum;
        result[1] = tmp ^ xorSum;
        Util.dumpArray(result);
        return result;
    }

    /**
     * 编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为 汉明重量）。
     * <p>
     * 思路1:暴力移位
     * 思路2:利用技巧: 提取n最右侧的1： n&((~n)+1)
     */

    public int hammingWeight(int n) {
        int result = 0;
        int mask = 0;
        while (n > 0) {
            mask = n & ((~n) + 1);
            result++;
            //将右侧的1抹零 or n&(n-1)
            n ^= mask;
        }
        return result;
    }

    /**
     * @param x
     * @param y
     * @return
     */
    int hammingDistance(int x, int y) {
        int n = x ^ y;
        int ret = 0;
        while (n != 0) {
            n = n & (n - 1);
            ret++;
        }
        return ret;
    }

    /**
     * 371. 两整数之和
     * 给你两个整数 a 和 b ，不使用 运算符 + 和 - 计算并返回两整数之和。
     * 思路:
     * 1. a & b里面包含进位信息 向高位移动一位作为进位
     * 2. a ^ b表示无进位和，需要和步骤1的进位做运算
     * 3. 循环步骤1和2，直到没有进位
     */
    public static int getSum(int a, int b) {
        while (b > 0) {//没有进位则退出
            //先计算本次运算有没有产生进位?
            int carry = (a & b) << 1;
            //本次计算的结果
            a = a ^ b;
            //产生的进位用于下次运算
            b = carry;
        }
        return a;
    }
}
